翻訳と辞書 Words near each other ・ Chomphu ・ Chomphu, Lampang ・ Chomphu, Phitsanulok ・ Chompion ・ Chompon Buangam ・ Chompoo Sangpo ・ Chomranice ・ Chomrieng Et Preang Tuok ・ Chomski ・ Chomsky (band) ・ Chomsky (disambiguation) ・ Chomsky (surname) ・ Chomsky hierarchy ・ Chomsky normal form ・ Chomsky–Schützenberger enumeration theorem ・ Chomsky–Schützenberger representation theorem ・ Chomsky–Schützenberger theorem ・ Chomu ・ Chomu (Rajasthan Assembly constituency) ・ Chomukha Bhairavji Temple ・ Chomutice ・ Chomutov ・ Chomutov District ・ Chomutov Zoo ・ Chomutov–Vejprty/Reitzenhain railway ・ Chomérac ・ Chomýž ・ Chomątowo ・ Chomęc ・ Chomęcice Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Chomsky–Schützenberger representation theorem ： ウィキペディア英語版 Chomsky–Schützenberger representation theorem In formal language theory, the Chomsky–Schützenberger representation theorem is a theorem derived by Noam Chomsky and Marcel-Paul Schützenberger about representing a given context-free language in terms of two simpler languages. These two simpler languages, namely a regular language and a Dyck language, are combined by means of an intersection and a homomorphism. A few notions from formal language theory are in order. A context-free language is ''regular'', if can be described by a regular expression, or, equivalently, if it is accepted by a finite automaton. A homomorphism is based on a function $h$ which maps symbols from an alphabet $\backslash Gamma$ to words over another alphabet $\backslash Sigma$; If the domain of this function is extended to words over $\backslash Gamma$ in the natural way, by letting $h(xy)=h(x)h(y)$ for all words $x$ and $y$, this yields a ''homomorphism'' $h:\backslash Gamma^$ *\to \Sigma^ *. A ''matched alphabet'' $T\; \backslash cup\; \backslash overline\; T$ is an alphabet with two equal-sized sets; it is convenient to think of it as a set of parentheses types, where $T$ contains the opening parenthesis symbols, whereas the symbols in $\backslash overline\; T$ contains the closing parenthesis symbols. For a matched alphabet $T\; \backslash cup\; \backslash overline\; T$, the ''Dyck language'' $D\_T$ is given by :$D\_T\; =\; \backslash$ words that are well-nested parentheses over $T\; \backslash cup\; \backslash overline\; T$. :Chomsky–Schützenberger theorem. A language ''L'' over the alphabet $\backslash Sigma$ is context-free if and only if there exists : * a matched alphabet $T\; \backslash cup\; \backslash overline\; T$ : * a regular language $R$ over $T\; \backslash cup\; \backslash overline\; T$, : * and a homomorphism $h\; :\; (T\; \backslash cup\; \backslash overline\; T)^$ * \to \Sigma^ * :such that $L\; =\; h(D\_T\; \backslash cap\; R)$. Proofs of this theorem are found in several textbooks, e.g. or . ==References== * * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chomsky–Schützenberger representation theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.